package com.stefan.queue;
/*
* 思路
* 数组方式实现的循环 - 加入数组capacity是10，那么第11个元素就是覆盖第一个tail =  (tail + 1) % capacity
* head = (head + 1) % capacity
* queue的是FIFO，所以头取数据，尾插数据，这里定义2个index，一个head，取数据的index，tail放数据的index
* 定义一个size，插入数据 size++，取数据size--，用size判断队列是否满是否空，
* 通过size判断队列满，队列空 变相防止一下两种情况发生，循环写入的时候tail 追上 head （如果追上，size > capacity）
* head 追上 tail (size <0),
*
* */
public class ArrayStefanQueue<E> implements StefanQueue<E>{
    //数据的载体，采用数组实现
    private Object[] elements;
    //数组容量
    private int capacity;
    //head指针 - 数组实现的话可以理解出队的index - 头取
    private int head;
    //tail指针 - 数组实现的话可以理解是入队的index - 尾插法
    private int tail;
    //数组的数据size
    int size;

    public ArrayStefanQueue () {
        //数组的话一般给个初始容量
        this.capacity = 10;
        elements = new Object[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }
    public ArrayStefanQueue (int capacity) {
        //数组的话一般给个初始容量
        this.capacity = capacity;
        elements = new Object[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    @Override
    public void enqueue(E element) {
        //入队的话要判断队列是不是满了
        if (isFull()) {
            //循环链表 - 从头开始放.
            return; //丢弃
        }
        elements[tail] = element;
        size++;
        /*这是个下一个元素的index，举个例子，这个数组capacity是6，
        *假设这是第一轮的最后一个元素，此时tail = 5，elements[5]是最后一个元素
        * 下一个元素如果可以放的话先要保证数组不是满的，是不是要放到element[0]
        * 那tail怎么变成0？ (tail+1)%capacity, 以此类推就是这个formula
        * 如果不是循环放入这里就是tail++
         */
        tail = (tail+1)%capacity;
    }

    @Override
    public E dequeue() {
        //出队时候判断队列是不是为空
        if (isEmpty()) {
            return null;
        }
        size--;
        E element = (E) elements[head];
        head = (head+1)%capacity;
        return element;
    }

//    @Override
//    public E peek() {
//        return null;
//    }
    @Override
    public boolean isFull() {
        return this.size == this.capacity;
    }
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
    @Override
    public int size() {
        return this.size;
    }

    public static void main(String[] args) {
        StefanQueue<Integer> stefanQueue = new ArrayStefanQueue<>(5);
        stefanQueue.enqueue(1);
        stefanQueue.enqueue(2);
        stefanQueue.enqueue(3);
        stefanQueue.enqueue(4);
        stefanQueue.enqueue(5);
        stefanQueue.enqueue(6); //队列满了，放不进
        System.out.println("======");
        System.out.println(stefanQueue.dequeue());//消费 1
        stefanQueue.enqueue(6);//在放，1的位置应该是6
        stefanQueue.enqueue(7);//在放，队列满了，放不进
        System.out.println(stefanQueue.dequeue());//消费2
        stefanQueue.enqueue(7);//2的位置为7
        System.out.println(stefanQueue.dequeue());//消费3
        System.out.println(stefanQueue.dequeue());//消费4
        System.out.println(stefanQueue.dequeue());//消费5
        System.out.println(stefanQueue.dequeue());//消费6
        System.out.println(stefanQueue.dequeue());//消费7
        System.out.println(stefanQueue.dequeue());//队列为空，消费不了
        stefanQueue.enqueue(8);//3的位置为8
        stefanQueue.enqueue(9);//4的位置为9
        stefanQueue.enqueue(10);//5的位置为10
        System.out.println("=====");

    }
}
